import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>() ;
        int len = nums.length ;
        Arrays.sort(nums);
        for(int i = 0 ; i <len ;){
            if(target < 0 && nums[i] >0){
                break ;
            }
            for(int j = i+1 ; j < len ; ){
                int left = j+1 ;
                int right = len-1 ;
                long sum =(long) target-nums[i]-nums[j];
                while(left<right){
                    int val = nums[left]+nums[right];
                    if(val > sum){
                        right -- ;
                    }else if(val < sum){
                        left ++ ;
                    }else{
                        list.add(new ArrayList<Integer>(Arrays.asList(nums[left],
                                nums[right],nums[i],nums[j])));
                        left ++ ;
                        right--;
                        while(left<right && nums[left]==nums[left-1]){
                            left++ ;
                        }
                        while(left<right && nums[right]==nums[right+1]){
                            right-- ;
                        }
                    }
                }
                j ++ ;
                while(j < len && nums[j]==nums[j-1]){
                    j++ ;
                }
            }
            i++ ;
            while(i < len && nums[i]==nums[i-1]){
                i++ ;
            }
        }
        return list ;
    }
}